import java.util.*;

public class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed == null || popped == null || pushed.length != popped.length) return false;
        Stack<Integer> stack = new Stack<>();
        int pu = 0;
        for (int item : popped) {
            if (stack.empty() || stack.peek() != item) {
                if (pu > pushed.length - 1) return false;
                do {
                    stack.push(pushed[pu++]);
                } while (pu < pushed.length - 1 && pushed[pu - 1] != item);
            }
            if (stack.peek() == item) {
                stack.pop();
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] pushed = {1, 2, 3, 4, 5};
        int[] popped = {4, 5, 3, 1, 2};
        System.out.println(new Solution().validateStackSequences(pushed, popped));
    }
}
